import java.util.*;

/**
 * @Author: YCKOKO
 * @Date: 2023-04-06
 * @Time:17:36
 * @Description:
 */
public class Graph3 {
    class Edge{
        int dest;
        int weight;
        public Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
    private static int INF = Integer.MAX_VALUE;
    private Map<Integer,List<Edge>> graph;

    public Graph3() {
        this.graph = new HashMap<>();
    }

    //添加结点
    public void addVertex(int vertex){
        graph.put(vertex,new ArrayList<>());
    }

    //添加有向边
    public void addDirectedEdge(int src,int dest,int weight){
        List<Edge> edges = graph.get(src);
        edges.add(new Edge(dest,weight));
    }

    //添加无向边
    public void addUndirectedEdge(int src,int dest,int weight){
        addDirectedEdge(src,dest,weight);
        addDirectedEdge(dest,src,weight);
    }

    public List<Edge> getNighbors(int vertex){
        return graph.get(vertex);
    }

    // 获取图的所有节点
    public Set<Integer> getVertex(){
        return graph.keySet();
    }

    // 判断两个节点是否有边相连
    public boolean hasEdge(int src,int dest){
        List<Edge> edges = graph.get(src);
        for (Edge edge: edges) {
            if(edge.dest == dest){
                return true;
            }
        }
        return false;
    }

    // 获取两个节点之间的边的权值
    public int getWeight(int src,int dest){
        List<Edge> edges = graph.get(src);
        for (Edge edge: edges) {
            if(edge.dest == dest){
                return edge.weight;
            }
        }
        return -1;
    }

    public void showGraph(){
        for (int vertex: graph.keySet()) {
            System.out.print(vertex + "->");
            List<Edge> edges = graph.get(vertex);
            for (Edge edge:edges) {
                System.out.print(edge.dest + "(" + edge.weight + ")" + " ");
            }
            System.out.println();
        }
    }
    //深度优先遍历
    public void dfs(int start){
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start,visited);
        System.out.println();
    }

    public void dfsHelper(int start,Set<Integer> visited){
        visited.add(start);
        System.out.print(start + " ");
        List<Edge> neighbors = graph.get(start);
        for (Edge edge: neighbors) {
            if(!visited.contains(edge.dest)){
                dfsHelper(edge.dest,visited);
            }
        }
    }

    //广度优先搜索
    public void bfs(int start){
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            System.out.print(cur + " ");
            List<Edge> edges = graph.get(cur);
            for (Edge edge: edges) {
                if(!visited.contains(edge.dest)){
                    queue.offer(edge.dest);
                    visited.add(edge.dest);
                }
            }
        }
        System.out.println();
    }


    public static void main(String[] args) {
        Graph3 graph = new Graph3();

        //添加顶点vertex
        graph.addVertex(0);
        graph.addVertex(1);
        graph.addVertex(2);
        graph.addVertex(3);

        //添加边Edge
        graph.addDirectedEdge(0, 1, 10);
        graph.addDirectedEdge(0, 2, 20);
        graph.addDirectedEdge(1, 2, 5);
        graph.addDirectedEdge(2, 3, 15);
        graph.addUndirectedEdge(1, 3, 20);

        graph.showGraph();

//        List<Edge> neighbors = graph.getNighbors(1);
//        for (Edge edge: neighbors) {
//            System.out.print(edge.dest + " ");
//        }
//        System.out.println();
//
//        System.out.println(graph.hasEdge(1, 4));
//        System.out.println(graph.hasEdge(1, 3));
//
//        System.out.println(graph.getVertex());
//
//        System.out.println(graph.getWeight(1, 2));

        graph.dfs(2);
        graph.bfs(1);
    }


}
